Alphabet (formal languages)

 ( Formal Languages ) 

In formal language theory, an alphabet, sometimes called a vocabulary (see Nonterminal Symbols), is a non-empty set of indivisible symbols/characters/,

typically thought of as representing letters, characters, digits, phonemes, or even words.

(1994). 9780387942582, Springer. . ISBN 9780387942582

Kenneth H. Rosen (2025). 9780073383095, McGraw Hill. . ISBN 9780073383095

The definition is used in a diverse range of fields including logic, mathematics, computer science, and linguistics. An alphabet may have any cardinality ("size") and, depending on its purpose, may be Finite set (e.g., the alphabet of letters "a" through "z"), countable (e.g., $\backslash \{v\_1,\; v\_2,\; \backslash ldots\backslash \}$), or even uncountable (e.g., $\backslash \{v\_x\; :\; x\; \backslash in\; \backslash mathbb\{R\}\; \backslash \}$).

Strings, also known as "words" or "sentences", over an alphabet are defined as a sequence of the symbols from the alphabet set.

For example, the alphabet of lowercase letters "a" through "z" can be used to form English words like "iceberg" while the alphabet of both upper and lower case letters can also be used to form proper names like "Wikipedia". A common alphabet is {0,1}, the binary alphabet, and "00101111" is an example of a binary string. Infinite sequences of symbols may be considered as well (see Omega language).

It is often necessary for practical purposes to restrict the symbols in an alphabet so that they are unambiguous when interpreted. For instance, if the two-member alphabet is {00,0}, a string written on paper as "000" is ambiguous because it is unclear if it is a sequence of three "0" symbols, a "00" followed by a "0", or a "0" followed by a "00".

---

Notation By definition, the alphabet of a formal language $L$ over $\backslash Sigma$ is the set $\backslash Sigma$, which can be any non-empty set of symbols from which every string in $L$ is built. For example, the set $\backslash Sigma\; =\; \backslash \{\backslash \_,\backslash mathrm\{a\},\; \backslash dots,\; \backslash mathrm\{z\},\; \backslash mathrm\{A\},\; \backslash dots,\; \backslash mathrm\{Z\},\; 0,\; \backslash mathrm\{1\},\; \backslash dots,\; \backslash mathrm\{9\}\backslash \}$ can be the alphabet of the formal language $L$ that means "all variable identifiers in the C programming language". Notice that it is not required to use every symbol in the alphabet of $L$ for its strings.

Given an alphabet $\backslash Sigma$, the set of all strings of length $n$ over the alphabet $\backslash Sigma$ is indicated by $\backslash Sigma^n$. The set $\backslash bigcup\_\{i\; \backslash in\; \backslash mathbb\{N\}\}\; \backslash Sigma^i$ of all finite strings (regardless of their length) is indicated by the Kleene star operator as $\backslash Sigma^*$, and is also called the Kleene closure of $\backslash Sigma$. The notation $\backslash Sigma^\backslash omega$ indicates the set of all infinite sequences over the alphabet $\backslash Sigma$, and $\backslash Sigma^\backslash infty$ indicates the set $\backslash Sigma^\backslash ast\; \backslash cup\; \backslash Sigma^\backslash omega$ of all finite or infinite sequences.

For example, using the binary alphabet {0,1}, the strings ε, 0, 1, 00, 01, 10, 11, 000, etc. are all in the Kleene closure of the alphabet (where ε represents the empty string).

---

Applications Alphabets are important in the use of formal languages, Automata theory and semiautomaton. In most cases, for defining instances of automata, such as deterministic finite automata (DFAs), it is required to specify an alphabet from which the input strings for the automaton are built. In these applications, an alphabet is usually required to be a finite set, but is not otherwise restricted.

When using automata, regular expressions, or as part of string-processing , the alphabet may be assumed to be the character set of the text to be processed by these algorithms, or a subset of allowable characters from the character set.

---

See also

• Combinatorics on words
• Terminal and nonterminal symbols

---

Literature

• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. .

Post Comment